<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(C卷,100分)- 会议室占用时间（Java & JS & Python & C）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>现有若干个会议&#xff0c;所有会议共享一个会议室&#xff0c;用数组表示各个会议的开始时间和结束时间&#xff0c;格式为&#xff1a;</p> 
<blockquote> 
 <p>[[会议1开始时间, 会议1结束时间], [会议2开始时间, 会议2结束时间]]</p> 
</blockquote> 
<p>请计算会议室占用时间段。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>第一行输入一个整数 n&#xff0c;表示会议数量</p> 
<p>之后输入n行&#xff0c;每行两个整数&#xff0c;以空格分隔&#xff0c;分别表示会议开始时间&#xff0c;会议结束时间</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>输出多行&#xff0c;每个两个整数&#xff0c;以空格分隔&#xff0c;分别表示会议室占用时间段开始和结束</p> 
<p></p> 
<h4>备注</h4> 
<ul><li>会议室个数范围&#xff1a;[1, 100]</li><li>会议室时间段&#xff1a;[1, 24]</li></ul> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">4<br /> 1 4<br /> 2 5<br /> 7 9<br /> 14 18</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">1 5<br /> 7 9<br /> 14 18</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;"> <p>输入&#xff1a;[[1,4],[2,5],[7,9],[14,18]]</p> <p>输出&#xff1a;[[1,5],[7,9],[14,18]]</p> <p>说明&#xff1a;时间段[1,4]和[2,5]重叠&#xff0c;合并为[1,5]</p> </td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:85px;">输入</td><td style="width:413px;">2<br /> 1 4<br /> 4 5</td></tr><tr><td style="width:85px;">输出</td><td style="width:413px;">1 5</td></tr><tr><td style="width:85px;">说明</td><td style="width:413px;"> <p>输入&#xff1a;[[1,4],[4,5]]</p> <p>输出&#xff1a;[[1,5]]</p> <p>说明&#xff1a;时间段[1,4]和[4,5]连续</p> </td></tr></tbody></table> 
<h4></h4> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题实际考试时为核心代码模式&#xff0c;非ACM模式&#xff0c;即无需处理输入输出。</p> 
<p>本博客代码实现仍然以ACM模式处理&#xff0c;但是会将 &#34;输入输出处理&#34; 与 &#34;核心代码&#34; 分开&#xff0c;大家只看核心代码即可。</p> 
<p></p> 
<p>本题是区间合并问题。</p> 
<p>我们可以将所有区间开始起始位置升序&#xff0c;然后取出第一个区间作为基准值pre&#xff0c;从第二个区间cur开始遍历&#xff1a;</p> 
<ul><li>如果 cur.start &lt;&#61; pre.end&#xff0c;则说明两个区间有重叠&#xff0c;此时我们应该将两个区间合并&#xff0c;合并策略是将pre.end &#61; <span style="color:#fe2c24;"><strong>max</strong></span>(pre.end, cur.end)&#xff0c;比如&#xff1a;<br /><br /> pre &#61; [1, 4]&#xff0c;cur &#61; [2, 5]&#xff0c;那么按此策略合并后&#xff0c;pre &#61; [1, 5]<br /><br /> pre &#61; [1, 100]&#xff0c;cur &#61; [7, 9]&#xff0c;那么按此策略合并后&#xff0c;pre &#61; [1, 100]<br />  </li><li>如果 cur.start &gt; pre.end&#xff0c;则说明两个区间无交集&#xff0c;此时pre无法和后面任何区间合并&#xff08;因为已经按照开始时间升序了&#xff0c;后面区间的开始时间肯定也大于pre.end&#xff09;&#xff0c;此时pre时间段就是一个独立的会议室占用时间&#xff0c;我们将它缓存记录下来&#xff0c;并将更新pre &#61; cur&#xff0c;即将cur作为新的基准值和后面的区间比较</li></ul> 
<p>按此逻辑&#xff0c;即可完成所有区间的合并。</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JS算法源码</h4> 
<pre><code class="language-javascript">const rl &#61; require(&#34;readline&#34;).createInterface({ input: process.stdin });
var iter &#61; rl[Symbol.asyncIterator]();
const readline &#61; async () &#61;&gt; (await iter.next()).value;

// 输入输出处理
void (async function () {
  const n &#61; parseInt(await readline());

  const roomTimes &#61; [];
  for (let i &#61; 0; i &lt; n; i&#43;&#43;) {
    roomTimes.push((await readline()).split(&#34; &#34;).map(Number));
  }

  merge(roomTimes).forEach(([start, end]) &#61;&gt; console.log(&#96;${start} ${end}&#96;));
})();

// 本题实际考试时会核心代码模式&#xff0c;无需处理输入输出&#xff0c;只需要写出merge方法实现即可
function merge(roomTimes) {
  // 将各个会议按照开始时间升序
  roomTimes.sort((a, b) &#61;&gt; a[0] - b[0]);

  // 记录合并后的会议室占用时间段
  const ans &#61; [];

  // 上一个会议占用时间段
  let pre &#61; roomTimes[0];
  for (let i &#61; 1; i &lt; roomTimes.length; i&#43;&#43;) {
    // 当前会议占用时间段
    const cur &#61; roomTimes[i];

    if (cur[0] &lt;&#61; pre[1]) {
      // 当前会议开始时间 &lt;&#61; 上一个会议结束时间&#xff0c;则两个会议时间重叠&#xff0c;可以合并
      // 注意合并时&#xff0c;结束时间取两个时间段中较大的结束时间
      pre[1] &#61; Math.max(pre[1], cur[1]);
    } else {
      // 否则不可以合并
      ans.push(pre);
      pre &#61; cur;
    }
  }

  ans.push(pre);

  return ans;
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
  // 输入输出处理
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    int n &#61; sc.nextInt();

    int[][] roomTimes &#61; new int[n][2];
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
      roomTimes[i][0] &#61; sc.nextInt();
      roomTimes[i][1] &#61; sc.nextInt();
    }

    int[][] res &#61; new Main().merge(roomTimes);
    for (int[] time : res) {
      System.out.println(time[0] &#43; &#34; &#34; &#43; time[1]);
    }
  }

  // 本题实际考试时会核心代码模式&#xff0c;无需处理输入输出&#xff0c;只需要写出merge方法实现即可
  public int[][] merge(int[][] roomTimes) {
    // 将各个会议按照开始时间升序
    Arrays.sort(roomTimes, (a, b) -&gt; a[0] - b[0]);

    // 记录合并后的会议室占用时间段
    ArrayList&lt;int[]&gt; list &#61; new ArrayList&lt;&gt;();

    // 上一个会议占用时间段
    int[] pre &#61; roomTimes[0];

    for (int i &#61; 1; i &lt; roomTimes.length; i&#43;&#43;) {
      // 当前会议占用时间段
      int[] cur &#61; roomTimes[i];

      if (cur[0] &lt;&#61; pre[1]) {
        // 当前会议开始时间 &lt;&#61; 上一个会议结束时间&#xff0c;则两个会议时间重叠&#xff0c;可以合并
        // 注意合并时&#xff0c;结束时间取两个时间段中较大的结束时间
        pre[1] &#61; Math.max(pre[1], cur[1]);
      } else {
        // 否则不可以合并
        list.add(pre);
        pre &#61; cur;
      }
    }

    list.add(pre);

    return list.toArray(new int[0][]);
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 本题实际考试时会核心代码模式&#xff0c;无需处理输入输出&#xff0c;只需要写出merge方法实现即可
def merge(roomTimes):
    # 将各个会议按照开始时间升序
    roomTimes.sort(key&#61;lambda x: x[0])

    # 记录合并后的会议室占用时间段
    ans &#61; []

    # 上一个会议占用时间段
    pre &#61; roomTimes[0]
    for i in range(1, len(roomTimes)):
        # 当前会议占用时间段
        cur &#61; roomTimes[i]

        if cur[0] &lt;&#61; pre[1]:
            # 当前会议开始时间 &lt;&#61; 上一个会议结束时间&#xff0c;则两个会议时间重叠&#xff0c;可以合并
            # 注意合并时&#xff0c;结束时间取两个时间段中较大的结束时间
            pre[1] &#61; max(pre[1], cur[1])
        else:
            # 否则不可以合并
            ans.append(pre)
            pre &#61; cur

    ans.append(pre)

    return ans


# 输入输出处理
n &#61; int(input())

roomTimes &#61; []
for _ in range(n):
    roomTimes.append(list(map(int, input().split())))

for start, end in merge(roomTimes):
    print(f&#34;{start} {end}&#34;)

</code></pre> 
<p></p> 
<h4>C算法源码</h4> 
<pre><code class="language-cpp">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

int rows &#61; 0;

int cmp(const void *a, const void *b) {
    return (*(int **) a)[0] - (*(int **) b)[0];
}

// 本题实际考试时会核心代码模式&#xff0c;无需处理输入输出&#xff0c;只需要写出merge方法相关实现即可
int **merge(int **roomTimes, int roomTimes_size) {
    // 将各个会议按照开始时间升序
    qsort(roomTimes, roomTimes_size, sizeof(int *), cmp);

    // 记录合并后的会议室占用时间段
    int** res &#61; (int**) malloc(sizeof(int*) * roomTimes_size);

    // 上一个会议占用时间段
    int* pre &#61; roomTimes[0];

    // 当前会议占用时间段
    for(int i&#61;1; i&lt;roomTimes_size; i&#43;&#43;) {
        int* cur &#61; roomTimes[i];

        if(cur[0] &lt;&#61; pre[1]) {
            // 当前会议开始时间 &lt;&#61; 上一个会议结束时间&#xff0c;则两个会议时间重叠&#xff0c;可以合并
            // 注意合并时&#xff0c;结束时间取两个时间段中较大的结束时间
            if(cur[1] &gt; pre[1]) {
                pre[1] &#61; cur[1];
            }
        } else {
            res[rows&#43;&#43;] &#61; pre;
            pre &#61; cur;
        }
    }

    res[rows&#43;&#43;] &#61; pre;

    return res;
}

// 输入输出处理
int main() {
    int n;
    scanf(&#34;%d&#34;, &amp;n);

    int **roomTimes &#61; (int **) malloc(sizeof(int *) * n);
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
        roomTimes[i] &#61; (int *) malloc(sizeof(int) * 2);
        scanf(&#34;%d %d&#34;, &amp;roomTimes[i][0], &amp;roomTimes[i][1]);
    }

    int **res &#61; merge(roomTimes, n);

    for (int i &#61; 0; i &lt; rows; i&#43;&#43;) {
        printf(&#34;%d %d\n&#34;, res[i][0], res[i][1]);
    }

    return 0;
}</code></pre> 
<p></p>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>